
//打家劫舍II
class Solution {
    public static int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + rob2(nums,2,n-1),rob2(nums,1,n-1));
    }

    private static int rob2(int[] nums,int left,int right){
        if(left >= right) return 0;

        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        for(int i = left;i < n;i++){
            f[i] = nums[i] + g[i - 1];
            g[i] = Math.max(g[i-1],f[i -1]);
        }

        return Math.max(f[right],g[right]);
    }

    public static void main(String[] args) {
        System.out.println(Solution.rob(new int[]{1,2,3}));
    }
}